#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <cmath>
#include <string>
#include <cassert>
#include <deque>
#include <ctime>
#include <windows.h>
using namespace std;

template<typename T>
class FastInsertionArray
{
	struct Node
	{
		Node() {clear(); }
		Node(const T &val): value(val) {clear(); }

		void clear()
		{
			lchild = rchild = parent = NULL;
			priority = rand();
			treeSize = 1;
		}

		Node *lchild;
		Node *rchild;
		Node *parent;
		T value;
		unsigned int priority;
		unsigned int treeSize;
	};

public:
	class iterator
	{
	public:
		typedef random_access_iterator_tag iterator_category;
		typedef T value_type;
		typedef ptrdiff_t difference_type;
		typedef difference_type distance_type;	// retained
		typedef T* pointer;
		typedef T& reference;

		iterator(FastInsertionArray *arr, Node *nd, unsigned int i): fia(arr), node(nd), idx(i) {}

		//iterator(const iterator &other);
		//iterator& operator=(const iterator &other);

		reference operator*() const { return node->value; }
		pointer operator->() const { return &(operator*()); }

		bool operator==(const iterator &other) { return node == other.node; }
		bool operator!=(const iterator &other) { return !(*this == other); }

		bool operator<(const iterator &other)
		{
			return idx < other.idx; 
		}

		bool operator<=(const iterator &other)
		{ 
			return idx <= other.idx;
		}

		bool operator>(const iterator &other)
		{
			return idx > other.idx;
		}

		bool operator>=(const iterator &other)
		{
			return idx >= other.idx;
		}


		iterator& operator++()
		{
			++idx;
			unsigned int sz = fia->size();
			if (idx < sz)
				nextNode();
			else if (idx == sz)
				node = NULL;
			else
				throw std::exception("Out of range.");

			return *this;
		}

		iterator operator++(int)
		{
			iterator tmp = *this;
			++(*this);
			return tmp;
		}

		iterator& operator--() 
		{ 
			--idx;
			int sz = (int)fia->size();
			if (idx >= 0 && idx < sz - 1)
				prevNode();
			else if (idx == sz - 1)
				node = fia->getNode(fia->root, sz - 1);
			else
				throw std::exception("Out of range.");

			return *this; 
		}

		iterator operator--(int)
		{
			iterator tmp = *this;
			--(*this);
			return tmp;
		}

		iterator& operator+=(int step)
		{
			idx += step;
			int sz = (int)fia->size();
			if (idx >= 0 && idx < sz)
				node = fia->getNode(fia->root, idx);
			else if (idx == sz)
				node = NULL;
			else
				throw std::exception("Out of range.");

			return *this;
		}

		iterator operator+(int step)
		{
			iterator tmp = *this;
			tmp += step;
			return tmp;
		}

		iterator& operator-=(difference_type step)
		{
			idx -= step;
			int sz = (int)fia->size();
			if (idx >= 0 && idx < sz)
				node = fia->getNode(fia->root, idx);
			else
				throw std::exception("Out of range.");

			return *this;
		}

		iterator operator-(difference_type step)
		{
			iterator tmp = *this;
			tmp -= step;
			return tmp;
		}
		
		difference_type operator-(const iterator &other)
		{
			return idx - other.idx;
		}


	    reference operator[](difference_type off)
		{
			return *(*this + off);
		}

	private:
		// node must has next node ,in operator++()
		// set node to its next
		void nextNode()
		{
			if (node->rchild)
			{
				node = node->rchild;
				while (node->lchild)
					node = node->lchild;
			}
			else
			{
				Node *y = node->parent;
				while (node == y->rchild)
				{
					node = y;
					y = y->parent;
				}
				node = y;
			}
		}

		// node must has prev node ,in operator--()
		// set node to its next
		void prevNode()
		{
			if (node->lchild)
			{
				node = node->lchild;
				while (node->rchild)
					node = node->rchild;
			}
			else
			{
				Node *y = node->parent;
				while (node == y->lchild)
				{
					node = y;
					y = y->parent;
				}
				node = y;
			}
		}

	private:
		Node *node;
		int idx;
		FastInsertionArray *fia;
	};

public:
	FastInsertionArray()
	{
		root = NULL;
		srand(time(0));
	}

	~FastInsertionArray()
	{
		clear();
	}

	iterator begin()
	{
		if (root == NULL)
			return end();
		return iterator(this, getNode(root, 0), 0);
	}

	iterator end()
	{
		return iterator(this, NULL, size());
	}

	T &operator[](unsigned int idx)
	{
		if (idx < size())
			return getNode(root, idx)->value;
		throw std::exception("Out of range.");
	}

	void push_back(const T &val)
	{
		insert(size(), val);
	}

	void push_front(const T &val)
	{
		insert(0, val);
	}

	void pop_back()
	{
		if (!empty())
			remove(size() - 1);
	}

	void pop_front()
	{
		if (!empty())
			remove(0);
	}

	bool insert(unsigned int idx, const T &val)
	{
		if (idx <= size())
		{
			if (root == NULL)
				root = new Node(val);
			else
			{
				if (idx == size())
					addRightestNode(root, val);
				else
					insertAtRank(root, idx, val);
			}
			return true;
		}
		return false;
	}

	bool remove(int idx)
	{
		if (idx < size())
		{
			Node *&tmp = getNode(root, idx, -1);
			removeNode(tmp);
			return true;
		}
		return false;
	}

	bool empty() const
	{
		return root == NULL;
	}

	unsigned int size() const
	{
		if (root == NULL)
			return 0;
		else
			return root->treeSize;
	}

	void clear()
	{
		destroy(root);
		root = NULL;
	}

	void printSequence()
	{
		printTree(root);
	}

private:
	Node *&getNode(Node *&nd, unsigned int idx, int sizeChanged = 0) const
	{
		if (nd == NULL)
			return nd;

		nd->treeSize += sizeChanged;

		unsigned int leftSize;
		if (nd->lchild == NULL)
			leftSize = 0;
		else
			leftSize = nd->lchild->treeSize;
		
		if (idx < leftSize)
			return getNode(nd->lchild, idx, sizeChanged);
		else if (idx == leftSize)
			return nd;
		else
			return getNode(nd->rchild, idx - leftSize - 1, sizeChanged);
	}

	void removeNode(Node *&nd)
	{
		Node *maxp = NULL;

		if (nd->lchild)
			maxp = nd->lchild;
		if (nd->rchild)
		{
			if (maxp == NULL)
				maxp = nd->rchild;
			else if (nd->rchild->priority > maxp->priority)
				maxp = nd->rchild;
		}

		if (maxp == NULL)
		{
			delete nd;
			nd = NULL;
		}
		else if (maxp == nd->lchild)
		{
			rotate_right_remove(nd);
			removeNode(nd->rchild);
		}
		else
		{
			rotate_left_remove(nd);
			removeNode(nd->lchild);
		}
	}

	void insertAtRank(Node *&nd, unsigned int idx, const T &val)
	{
		nd->treeSize++;

		unsigned int leftSize;
		if (nd->lchild == NULL)
			leftSize = 0;
		else
			leftSize = nd->lchild->treeSize;

		if (idx < leftSize)
		{
			insertAtRank(nd->lchild, idx, val);
			if (nd->lchild->priority > nd->priority)
				rotate_right(nd);
		}
		else if (idx == leftSize)
		{
			if (nd->lchild == NULL)
			{
				nd->lchild = new Node(val);
				nd->lchild->parent = nd;
				if (nd->lchild->priority > nd->priority)
					rotate_right(nd);
			}
			else
			{
				addRightestNode(nd->lchild, val);
				if (nd->lchild->priority > nd->priority)
					rotate_right(nd);
			}
		}
		else
		{
			insertAtRank(nd->rchild, idx - leftSize - 1, val);
			if (nd->rchild->priority > nd->priority)
				rotate_left(nd);
		}
	}

	void addRightestNode(Node *&nd, const T &val)
	{
		nd->treeSize++;

		if (nd->rchild == NULL)
		{
			nd->rchild = new Node(val);
			nd->rchild->parent = nd;
			if (nd->rchild->priority > nd->priority)
				rotate_left(nd);
		}
		else
		{
			addRightestNode(nd->rchild, val);
			if (nd->rchild->priority > nd->priority)
				rotate_left(nd);
		}
	}

	void rotate_left(Node *&tree)
	{
		Node *p = tree->parent;

		Node *rc = tree->rchild;
		tree->rchild = rc->lchild;
		rc->lchild = tree;
		tree = rc;

		tree->parent = p;
		tree->lchild->parent = tree;
		if (tree->lchild->rchild)
			tree->lchild->rchild->parent = tree->lchild;

		// adjust tree size
		unsigned int s1 = 0;
		if (tree->lchild->lchild != NULL)
			s1 += tree->lchild->lchild->treeSize;
		if (tree->lchild->rchild != NULL)
			s1 += tree->lchild->rchild->treeSize;
		tree->lchild->treeSize = s1 + 1;

		unsigned int s2 = tree->lchild->treeSize;
		if (tree->rchild != NULL)
			s2 += tree->rchild->treeSize;
		tree->treeSize = s2 + 1;
	}

	void rotate_right(Node *&tree)
	{
		Node *p = tree->parent;

		Node *lc = tree->lchild;
		tree->lchild = lc->rchild;
		lc->rchild = tree;
		tree = lc;

		tree->parent = p;
		tree->rchild->parent = tree;
		if (tree->rchild->lchild)
			tree->rchild->lchild->parent = tree->rchild;

		// adjust tree size
		unsigned int s1 = 0;
		if (tree->rchild->lchild != NULL)
			s1 += tree->rchild->lchild->treeSize;
		if (tree->rchild->rchild != NULL)
			s1 += tree->rchild->rchild->treeSize;
		tree->rchild->treeSize = s1 + 1;

		unsigned int s2 = tree->rchild->treeSize;
		if (tree->lchild != NULL)
			s2 += tree->lchild->treeSize;
		tree->treeSize = s2 + 1;
	}

	
	void rotate_left_remove(Node *&tree)
	{
		Node *p = tree->parent;

		Node *rc = tree->rchild;
		tree->rchild = rc->lchild;
		rc->lchild = tree;
		tree = rc;

		tree->parent = p;
		tree->lchild->parent = tree;
		if (tree->lchild->rchild)
			tree->lchild->rchild->parent = tree->lchild;

		// adjust tree size
		unsigned int s1 = 0;
		if (tree->lchild->lchild != NULL)
			s1 += tree->lchild->lchild->treeSize;
		if (tree->lchild->rchild != NULL)
			s1 += tree->lchild->rchild->treeSize;
		tree->lchild->treeSize = s1;

		unsigned int s2 = tree->lchild->treeSize;
		if (tree->rchild != NULL)
			s2 += tree->rchild->treeSize;
		tree->treeSize = s2 + 1;
	}

	void rotate_right_remove(Node *&tree)
	{
		Node *p = tree->parent;

		Node *lc = tree->lchild;
		tree->lchild = lc->rchild;
		lc->rchild = tree;
		tree = lc;
		
		tree->parent = p;
		tree->rchild->parent = tree;
		if (tree->rchild->lchild)
			tree->rchild->lchild->parent = tree->rchild;


		// adjust tree size
		unsigned int s1 = 0;
		if (tree->rchild->lchild != NULL)
			s1 += tree->rchild->lchild->treeSize;
		if (tree->rchild->rchild != NULL)
			s1 += tree->rchild->rchild->treeSize;
		tree->rchild->treeSize = s1;

		unsigned int s2 = tree->rchild->treeSize;
		if (tree->lchild != NULL)
			s2 += tree->lchild->treeSize;
		tree->treeSize = s2 + 1;
	}

	void printTree(Node *nd)
	{
		if (nd != NULL)
		{
			printTree(nd->lchild);
			printf("%d ", nd->value);
			printTree(nd->rchild);
		}
	}

	void destroy(Node *nd)
	{
		if (nd != NULL)
		{
			destroy(nd->lchild);
			destroy(nd->rchild);
			delete nd;
		}
	}

private:
	Node *root;
};



void test_insert()
{
	FastInsertionArray<int> mp;
	vector<int> vi;
	for (int i = 0; i < 1000; i++)
	{
		int p = rand() % (vi.size() + 1);
		int r = rand();
		vi.insert(vi.begin() + p, r);
		mp.insert(p, r);
	}
	assert(vi.size() == mp.size());
	for (int i = 0; i < vi.size(); i++)
	{
		//cout << vi[i] << '\t' << mp[i] << endl;
		assert(vi[i] == mp[i]);
	}
}

void test_remove()
{
	FastInsertionArray<int> mp;
	vector<int> vi;
	const int len = 10000;
	for (int i = 0; i < len; i++)
	{
		int p = rand() % (vi.size() + 1);
		int r = rand();
		vi.insert(vi.begin() + p, r);
		mp.insert(p, r);
	}
	assert(vi.size() == mp.size());
	for (int i = 0; i < vi.size(); i++)
		assert(vi[i] == mp[i]);

	for (int i = 0; i < len; i++)
	{
		int p = rand() % vi.size();
		assert(vi[p] == mp[p]);
		vi.erase(vi.begin() + p);
		mp.remove(p);
		assert(vi.size() == mp.size());
	}
	assert(vi.empty() == mp.empty());
}


void test_iterator()
{
	FastInsertionArray<int> mp;
	vector<int> vi;
	const int len = 10000;
	for (int i = 0; i < len; i++)
	{
		int r = rand() % (vi.size() + 1);
		int v = rand();
		vi.insert(vi.begin() + r, v);
		mp.insert(r, v);
	}
	vector<int>::iterator i = vi.begin();
	FastInsertionArray<int>::iterator j = mp.begin();
	for (; i != vi.end(); i++, j++)
		assert(*i == *j);
	assert(j == mp.end());

	i = vi.end() - 1;
	j = mp.end() - 1;
	for (; i != vi.begin(); i--, j--)
		assert(*i == *j);
	assert(j == mp.begin());

	// sort test
	sort(vi.begin(), vi.end(), greater<int>());
	sort(mp.begin(), mp.end(), greater<int>());
	i = vi.begin();
	j = mp.begin();
	for (; i != vi.end(); i++, j++)
		assert(*i == *j);

	// remove some elements
	for (int i = 0; i < len / 2; i++)
	{
		int r = rand() % vi.size();
		vi.erase(vi.begin() + r);
		mp.remove(r);
	}
	i = vi.begin();
	j = mp.begin();
	for (; i != vi.end(); i++, j++)
		assert(*i == *j);
	assert(j == mp.end());
	
	i = vi.end() - 1;
	j = mp.end() - 1;
	for (; i != vi.begin(); i--, j--)
		assert(*i == *j);
	assert(j == mp.begin());

}

void performanceTest()
{
	// RELEASE MODE
	vector<pair<int, int> > vpii;
	const int len = 200000;
	for (int i = 0; i < len; i++)
	{
		int p = rand() % (vpii.size() + 1);
		int r = rand();
		vpii.push_back(make_pair(p, r));
	}

	vector<int> vi;
	FastInsertionArray<int> mp;

	DWORD t1 = GetTickCount();
	for (int i = 0; i < len; i++)
		vi.insert(vi.begin() + vpii[i].first, vpii[i].second);
	DWORD t2 = GetTickCount();
	for (int i = 0; i < len; i++)
		mp.insert(vpii[i].first, vpii[i].second);
	DWORD t3 = GetTickCount();
 
	cout << t2 - t1 << endl << t3 - t2 << endl;
}

int main()
{	
	test_insert();
	test_remove();
	test_iterator();
	performanceTest();
	system("pause");
	return 0;
}